package foundation.search;


/**
 * @author hang an
 * @since 2025/7/8
 */
public class binarySearch {
    public static void main(String[] args) {
        int[] arr = {-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] arr1 = {-1, 0, 1, 2, 3, 3, 3, 4, 5, 5, 6, 7, 8, 9, 10};
        System.out.println(search(5, arr));
        System.out.println(searchFirstLeft(3, arr1));

        System.out.println(searchLastRight(3, arr1));
    }

    private static int search(int target, int[] arr) {
        int n = arr.length;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] == target) return mid;
            else if (target < arr[mid]) r = mid - 1;
            else l = mid + 1;
        }
        return -1;
    }

    // 寻找第一个大于等于target的数
    private static int searchFirstLeft(int target, int[] arr) {
        int n = arr.length;
        int l = 0, r = n - 1;
        int ans = -1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (target <= arr[mid]) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }

    // 寻找最后一个小于等于target的数
    private static int searchLastRight(int target, int[] arr) {
        int n = arr.length;
        int l = 0, r = n - 1;
        int ans = -1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] <= target) {
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }

}
